1. Field of the Invention
The present invention relates to a computer system for image processing, and relates in particular to a halftoning method and apparatus.
2. Background Description
As is shown in FIG. 1, according to a general and conventional error diffusion method, or an error distribution method, a quantization error occurring at a currently processed pixel is diffused throughout an area in its vicinity. As a result of this diffusion, a display error is reduced to generate a half tone image, where the half tone image is an image that has smaller tone levels for pixels than the original image.
In FIG. 1, assume that an input image is denoted by x(n1,n2) 105 and an output image is denoted by y(n1,n2) 125, and that the input image is obtained by raster scanning N1×N2 pixels. In this case, 0≦n1≦N1 and 0≦n2≦N2.
In FIG. 1, blocks 110 and 140 are adders, a block 120 is a quantizer, and a block 130 is an error diffusion filter.
A two-dimensional low-pass filter having causality is used as the filter g(n1,n2) 130 that diffuses a quantization error e(n1,n2) 145, and is represented by, for example, the following expression:       g    ⁡          (                        n          1                ,                  n          2                    )        =            [                                    0                                0                                0                                0                                0                                                0                                0                                0                                0                                0                                                0                                0                                0                                7                                5                                                3                                5                                7                                5                                3                                                1                                3                                5                                3                                1                              ]        ·          1      48      
In the above expression, the element (3,3) (the center element in a 5×5 matrix) corresponds to a pixel currently being processed. Using the common error diffusion method, however, when a quantization error is diffused by the filter, the characteristics of an image, such as a sharp change portion of pixel values, may be lost.
The employment of a halftoning image is especially effective for a display method on a device having a small display area, such as a wearable clock type system, a PDA or a portable telephone, or, for a display method during a shifting period in which data must be sequentially transmitted to an LCD for an image having a definition of QXGA (2048×1536) or higher because collective transmission is difficult for such high definition LCDs. However, when the common error diffusion method is used to transform an image to a half tone, important characteristics of an image, such as the image edges, are lost, and for a conventional improved method, an enormous number of calculations is required to prevent such deterioration. Therefore, for the above described application examples, it is difficult to use conventional methods.
In order to cope with the loss of image characteristics, a method [1] proposed by Couwenhoven, et. al. (U.S. Pat. No. 5,757,517, “Adaptive error diffusion method.” May 26, 1998 (filed on Mar. 23, 1995)), provides for an error diffusion ratio to be changed based on extracted characteristic information only, such as a high frequency component of the original image.
According to the method described in document [1], however, in order to apply extracted information, not only is error diffusion low-pass filtering required, but also other filtering must be performed in a quantizer and an output unit, so that the number of calculations is increased.
According to another method [2] proposed by Wong (“Adaptive error diffusion and its application in multi-resolution rendering,” P. W. Wong, IEEE Trans. Image Processing, vol. 5, No. 7, pp. 1184–1196, 1996), in accordance with an input/output image, an error diffusion filter is adaptively changed based on a local distortion criterion. When the method described in document [2] is used to adjust distortions of all the coefficients of the diffusion low-pass filter, however, based on the impulse response of a human visual characteristic model, a calculation using the least squares method is required for each pixel. Thus, as with the method described in document [1], there is an increase in the number of calculations must be performed.